package demo8;

import java.util.*;

class Edge {
    int src, dest, weight;

    Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

class Graph {
    int vertices;
    int[][] adjMatrix;

    Graph(int vertices) {
        this.vertices = vertices;
        adjMatrix = new int[vertices][vertices];
        for (int i = 0; i < vertices; i++) {
            Arrays.fill(adjMatrix[i], Integer.MAX_VALUE);
        }
    }

    void addEdge(int src, int dest, int weight) {
        adjMatrix[src][dest] = weight;
        adjMatrix[dest][src] = weight; // 无向图
    }

    void primMST(int start) {
        boolean[] selected = new boolean[vertices];
        selected[start] = true;
        int totalWeight = 0;
        List<Edge> mstEdges = new ArrayList<>();

        System.out.println("Prim算法的最小生成树边：");

        // 循环直到选出 vertices - 1 条边
        for (int edgeCount = 0; edgeCount < vertices - 1; edgeCount++) {
            int minWeight = Integer.MAX_VALUE;
            int x = -1, y = -1;

            // 寻找当前已选择节点相连的边中，权重最小的边
            for (int i = 0; i < vertices; i++) {
                if (selected[i]) { // 如果节点i已被选择
                    for (int j = 0; j < vertices; j++) {
                        if (!selected[j] && adjMatrix[i][j] < minWeight) {
                            minWeight = adjMatrix[i][j]; // 更新最小权重
                            x = i; // 记录边的起点
                            y = j; // 记录边的终点
                        }
                    }
                }
            }

            // 如果找到了合适的边，则更新状态
            if (x != -1 && y != -1) {
                System.out.println("边: " + x + " - " + y + " (权重: " + minWeight + ")");
                totalWeight += minWeight;
                selected[y] = true; // 选择该节点
                mstEdges.add(new Edge(x, y, minWeight));
            }
        }

        System.out.println("最小生成树的总权重（Prim算法）: " + totalWeight);
        displayMST(mstEdges);
    }


    void kruskalMST() {
        int edgeCount = 0;
        Edge[] edges = new Edge[(vertices * (vertices - 1)) / 2]; // 使用一维数组存储边

        for (int i = 0; i < vertices; i++) {
            for (int j = i + 1; j < vertices; j++) {
                if (adjMatrix[i][j] != Integer.MAX_VALUE) {
                    edges[edgeCount++] = new Edge(i, j, adjMatrix[i][j]);
                }
            }
        }

        Arrays.sort(edges, 0, edgeCount, Comparator.comparingInt(e -> e.weight));

        UnionFind unionFind = new UnionFind(vertices);
        int totalWeight = 0;
        List<Edge> mstEdges = new ArrayList<>();
        System.out.println("Kruskal算法的最小生成树边：");

        for (int i = 0; i < edgeCount; i++) {
            Edge edge = edges[i];
            if (!unionFind.isSameSet(edge.src, edge.dest)) {   // 避免构成环路
                System.out.println("边: " + edge.src + " - " + edge.dest + " (权重: " + edge.weight + ")");
                totalWeight += edge.weight;
                unionFind.union(edge.src, edge.dest);
                mstEdges.add(edge);
            }
        }
        System.out.println("最小生成树的总权重（Kruskal算法）: " + totalWeight);
        displayMST(mstEdges);
    }

    void displayMST(List<Edge> mstEdges) {
        System.out.println("构造出的最小生成树：");
        for (Edge edge : mstEdges) {
            System.out.println("节点 " + edge.src + " -- 节点 " + edge.dest + " （权重：" + edge.weight + "）");
        }
    }
}

class UnionFind {
    public int[] parent;
    public int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 基于大小的合并
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }
}

public class MSTSimulator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("**********************************************************************");
        System.out.println("*                                                                    ");
        System.out.println("*                最小生成树模拟程序                           ");
        System.out.println("*                                                                    ");
        System.out.println("*       1、普里姆（Prim）算法构造最小生成树                              ");
        System.out.println("*       2、克鲁斯卡尔（Kruskal）算法构造最小生成树                        ");
        System.out.println("*                                                                    ");
        System.out.println("**********************************************************************");

        int n = 6;
        Graph graph = new Graph(n);

        // 预设的无向连通网络
        graph.addEdge(0, 1, 7);
        graph.addEdge(0, 2, 5);
        graph.addEdge(1, 2, 9);
        graph.addEdge(1, 3, 8);
        graph.addEdge(2, 4, 7);
        graph.addEdge(3, 4, 6);
        graph.addEdge(3, 5, 2);
        graph.addEdge(4, 5, 3);


        System.out.println("请选择算法：");
        System.out.println("1. 普里姆（Prim）算法");
        System.out.println("2. 克鲁斯卡尔（Kruskal）算法");
        int choice = scanner.nextInt();

        if (choice == 1) {
            System.out.println("请输入起点编号进行Prim算法：");
            int start = scanner.nextInt();
            graph.primMST(start);
        } else if (choice == 2) {
            graph.kruskalMST();
        } else {
            System.out.println("无效的选择");
        }

        scanner.close();
    }
}

//   最小生成树在无向有权图中图形不是唯一的
//   Prim算法适合用于稠密图  Kruskal算法更适合用于稀疏图

/*
        (0)
       /   \
     7/     \5
     /   9   \
   (1)-------(2)
    |        |
   8|        |7
    |        |
   (3)---6---(4)
     \      /
       2   3
        \ /
        (5)
 */
